---

deOctree.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file deOctree.hpp
///
/// @brief octree for use in scenegraph, not for use outside scenegraph library
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// </hr>
///
/// @date Jun 2002
/// @author Assassin
/// @remarks Initial Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DEOCTREE_HPP
#define DEOCTREE_HPP

#include "deGlobalTypes.hpp"
#include "deScene.hpp"
#include "deList.hpp" // for collide info

#if defined(DESCENE_DLL_EXPORTS) || defined(DESTINY3D_EXPORT_ALL)
#   define DEOCTREE_API DEDLL_EXPORT
#elif defined(DESTINY3D_STATIC_LINK)
#   define DEOCTREE_API
#else
#   define DEOCTREE_API DEDLL_IMPORT
#endif

class IdeVertexBuffer;

class deSceneOctree
{
protected:
    virtual ~deSceneOctree();

public:
    deSceneOctree();
    int Release();

    void TEST();

    void SetMinOctSize(deDouble MinSize);
    deDouble GetMinOctSize();
    void SetMaxNodeNum(int MaxNum);
    int GetMaxNodeNum();

    IdeVertexBuffer * GetVB(int MaxPoints);
    
    deBoolean WipeTree();

    deBoolean AddNode(IdeSceneRoom * Node);
    deBoolean RemoveNode(IdeSceneRoom * Node);

    IdeSceneRoom * FindContainerNode(const deVec3d &Position);
    IdeSceneRoom * FindClosestNode(const deVec3d &Position);
    deBoolean FindIntersectingNodes(deTList <IdeSceneRoom*> &List, const deVec3d * Mins, const deVec3d * Maxs);

    deBoolean TraceRayCollision(const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo & Collision);

    void CleanUp();
    
private:
    enum Neighbor_t
    {
        n_None = -1,
        n_Left = 0,
        n_Right,
        n_Bottom,
        n_Top,
        n_Front,
        n_Back,
    };
    struct Octant
    {
        Octant* Parent;
        int ParentIndex;
        int NeighborRefs;
        Octant* Child[8];
        Octant* Neighbor[6];
        deTList <IdeSceneRoom*> FixedNodes;
        deTList <IdeSceneRoom*> AddedNodes;
        deVec3d Min, Max, Center;
        deBoolean CanBeRemoved;
        int TestNumber;
    };
    // root for the octant tree
    Octant * m_Root;
    // minimum dimension for an octant
    deDouble m_MinSize;
    // maximum number of objects to have in an octant. MinSize overrides this
    int m_MaxNodes;

    int m_TestNumber;

    IdeVertexBuffer * m_LineListVB;

    deBoolean FillOctantLinePoints(Octant * oct, deVertex * Buffer, int & LastPoint, int MaxPoints);

    void CleanUp(Octant * oct);
    deBoolean SubdivideOctant(Octant * oct);
    deBoolean Optimize(Octant * oct);
    deBoolean InsertNode(IdeSceneRoom * Node);

    deBoolean CalcNeighbors(Octant * oct);
    Octant* TraceNeighbor(Octant * Start, Octant * Current, Neighbor_t N, int Depth);

    deBoolean RayTestFromOctant(Octant * oct, const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo & Collision);
    deBoolean RayTestNodes(Octant * oct, const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo * Collision);
    deBoolean RayTestParents(Octant * oct, const deVec3d & Start, const deVec3d & Dir, IdeCollision::deCollideInfo * Collision);
    Neighbor_t RayToNeighbor(Octant * oct, const deVec3d & RayStart, const deVec3d & RayDir, deVec3d & ExitPoint);
    int DecideChildOctant(Octant * Parent, const deVec3d & Position);
    int DecideParentOctant(Octant * Child, const deVec3d & Position);
    
    deBoolean InitializeRoot();
    Octant * MakeOctant(const deVec3d &Min, const deVec3d &Max, Octant * ParentChild, int ParentID);
    Octant * MakeSubOctant(Octant * ParentChild, int ParentID);

    deBoolean RemoveOctant(Octant * oct, deTList <IdeSceneRoom*> * DumpList, deBoolean RemoveChildren, deBoolean IgnoreNeighbors = deFALSE);

    Octant * FindOctant(const deVec3d &Position);
    Octant * FindSubOctant(Octant * oct, const deVec3d &Position);
    Octant * FindOctant(const deVec3d &Min, const deVec3d &Max);
    Octant * FindSubOctant(Octant * oct, const deVec3d &Min, const deVec3d &Max);

    deBoolean TestOctantPoint(Octant * oct, const deVec3d &Position);
    deBoolean TestOctantBBox(Octant * oct, const deVec3d &Min, const deVec3d &Max);
};

#endif

---